/**
 * @param {number} n
 * @return {number}
 */
export var climbStairs = function (n) {
  if (n === 1) return 1
  if (n === 2) return 2
  let a = 1
  let b = 2
  for (let i = 3; i <= n; i++) {
    const c = a + b
    a = b
    b = c
  }
  return b
}

export var climbStairs2 = function (n) {
  if (n === 1) return 1
  if (n === 2) return 2
  return climbStairs2(n - 1) + climbStairs2(n - 2)
}
